package com.lw.leetcode.linked.b;

import com.lw.leetcode.linked.ListNode;

/**
 * leetcode 142. 环形链表 II
 * 面试题 02.08. 环路检测
 * 剑指 Offer II 022. 链表中环的入口节点
 *
 * @Author liw
 * @Date 2021/5/14 16:24
 * @Version 1.0
 */
public class DetectCycle {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode a = head;
        ListNode b = head;
        ListNode item = null;
        while (a != null && b != null) {
            a = a.next;
            if (b.next == null) {
                return null;
            }
            b = b.next.next;
            if (a == b) {
                item = a;
                break;
            }
        }
        if (item == null) {
            return null;
        }
        while (head != item) {
            head = head.next;
            item = item.next;
        }
        return head;
    }
}
